class TrieNode
{
public:
    vector<TrieNode*> child;
    bool isWord;
    TrieNode()
        : child(26, nullptr)
        , isWord(false)
    {};
    ~TrieNode()
    {
        for (auto e : child)
        {
            delete e;
        }
    }
};

class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* p = root;
        for (char e : word)
        {
            int i = e - 'a';
            if (!p->child[i])
                p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }
    
    bool search(string word) {
        return match(word, root, 0);
    }

    bool match(string& word, TrieNode* p, int start)
    {
        if (!p)
            return false;
        if (start == word.size())
            return p->isWord;
        char c = word[start];
        if (c != '.')
            return match(word, p->child[c - 'a'], start + 1);
        else
        {
            for (const auto& child : p->child)
            {
                if (match(word, child, start + 1))
                    return true;
            }
        }
        return false;
    }
private:
    TrieNode* root;
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */